// #include <iostream>
// #include <vector>
// #include <unordered_map>
// #include <unordered_set>
// using namespace std;
// typedef int TypeHashTable;
// #define MAX_SIZE 20
// #define key 7
// struct HashTable
// {
//     TypeHashTable HashKey;//哈希表的key
//     TypeHashTable HashVal;//哈希表的value
//     HashTable* HashTablePtr;//哈希表的头节点指针
//     HashTable* next;//指向下一个节点
// }Hash[MAX_SIZE];

// int GetIndex(int HashKey)
// {
//     return HashKey % key;
// }

// void HashTableInit(HashTable*& Hash)
// {

// }

// void HashTableInsert()
// {

// }

// void test()
// {

// }

// int main()
// {
//     test();
//     return 0;
// }

#include <bits/stdc++.h>
using namespace std;
// //滑动窗口和哈希表
// // class Solution {
// // public:
// //     bool containsNearbyDuplicate(vector<int>& nums, int k) {
// //         unordered_map<int,int> index;
// //         for(int i=0;i<nums.size();i++)
// //         {
// //             if(index.find(nums[i])!=index.end()&&abs(i-index[nums[i]])<=k)
// //                 return true;
// //             index[nums[i]]=i;
// //         }
// //         return false;
// //     }
// // };
// // 0 1 2 3
// // 1 2 3 4
// // 3
// class Solution {
// public:
//     bool containsNearbyDuplicate(vector<int>& nums, int k) {
//         unordered_set<int> st;
//         for(int i=0;i<nums.size();i++)
//         {
//             //保证一直能插入成功,
//             //如果插入失败则说明在min(k+1,n)中有已经存在相同的元素
//             //定长的窗口插入失败一定满足题目条件
//             if(!st.insert(nums[i]).second)return true;
//             //保证窗口的大小一直在min(k+1,n)
//             if(i>=k)st.erase(nums[i-k]);
//         }
//         return false;
//     }
// };

// int main()
// {
//     int n=0;
//     string s[1007];
//     while(cin>>s[++n]);
//     for(int i=n-1;i>=1;i--)
//     {
//         for(int j=0;j<static_cast<int>(s[i].size());j++)
//         {
//             if(s[i][j]>='a'&&s[i][j]<='z')
//                 s[i][j]-=32;
//             else if(s[i][j]>='A'&&s[i][j]<='Z')
//                 s[i][j]+=32;
//         }
//         //判断每个字符串首位是数字还是字符决定如何输出
//         if(s[i][0]>='0'&&s[i][0]<='9')
//             for(int j=s[i].size()-1;j>=0;j--)
//                 cout<<s[i][j];
        
//         else cout<<s[i];
//         if(i!=1)cout<<" ";
//     }
//     cout<<endl;
//     return 0;
// }
//时间和空间复杂度都是O(N)
// class Solution {
// public:
//     int firstMissingPositive(vector<int>& nums) {
//         vector<bool> v1(nums.size()+1,false);
//         for(int i=0;i<nums.size();i++)
//         {
//             if(nums[i]>0&&nums[i]<=nums.size())
//                 v1[nums[i]]=true;
//         }
//         for(int i=1;i<v1.size();i++)
//         {
//             if(!v1[i])return i;
//         }
//         return nums.size()+1;
//     }
// };
//时间复杂度是O(N),空间复杂度为O(1)
// class Solution {
// public:
//     int firstMissingPositive(vector<int>& nums) {
//         for(int i=0;i<nums.size();i++)
//         {
//             //nums[i]!=nums[nums[i]-1]保证每个数据能出现在值对应的下标
//             while(nums[i]>=1&&nums[i]<=nums.size()&&nums[i]!=nums[nums[i]-1])
//                 swap(nums[i],nums[nums[i]-1]);
//         }
//         for(int i=0;i<nums.size();i++)
//         {
//             if(nums[i]!=i+1)return i+1;
//         }
//         return nums.size()+1;
//     }
// };